//
// Created by napo on 22-11-20.
//

#ifndef CARP_SORT_H
#define CARP_SORT_H

#include "head.h"

void insertSort(int A[], int n) {
    int i,j,temp;
    for(i=1; i<n; ++i) {
        if(A[i] < A[i-1]) {
            temp = A[i];
            for(j=i-1; temp < A[j] && j >=0; j--) {
                A[j+1] = A[j];
            }
            A[j+1] = temp;
        }
    }
}

int partition(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot)
            high--;
        A[low] = A[high];
        while (low < high && A[low] <= pivot)
            low++;
        A[high] = A[low];
    }

    A[low] = pivot;
    return low;
}

void quickSort(int A[], int low, int high) {
    if(low < high) {
        int pivotpos = partition(A, low, high);
        partition(A, low, pivotpos-1);
        partition(A, pivotpos+1, high);
    }
}

#endif //CARP_SORT_H